/**
 * FileName: TestBFSAlgorithmsForAdjacenyMatrix.c
 * ----------------------------------------------------------------------------------------------------
 * 这是一份基于邻接矩阵的图的bfs应用代码
 * - 最短路径
 * - 单源头最短路径
 * - 图里所有顶点对的最短路径
 *
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "../../includes/QUEUE.h"

//边相关
// typedef struct {
//     int v;
//     int w;
// } Edge;

//图相关
typedef struct graph *Graph;
struct graph {
    int V;
    int E;
    int** adj;
};

#define bfs search

static int cnt;
static int* pre;
static int* st;

//辅助函数声明
void HELPinit(int);
void HELPcleanUp();
int** MATRIXinit(int, int, int);
Edge EDGE(int, int);
void GRAPHshow(Graph);
void bfs(Graph, Edge);
void print_shortest_path(int, int);
void print_shortest_pathR(int, int);

//图操作声明
Graph GRAPHinit(int);
void GRAPHinsertE(Graph, Edge);
void GRAPHremoveE(Graph, Edge);
int GRAPHedges(Edge [], Graph);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);
void GRAPHsearch(Graph);
void GRAPHsearch2(Graph, int);

//辅助函数实现
void HELPinit(int maxV) {
    //全局变量初始化
    cnt = 0;
    int v;
    pre = malloc(maxV * sizeof(int));
    for (v = 0; v < maxV; v++) {
        pre[v] = -1;
    }
    st = malloc(maxV * sizeof(int));
    for (v = 0; v < maxV; v++) {
        st[v] = -1;
    }
    QUEUEinit(maxV);
}

void HELPcleanUp() {
    free(pre);
    free(st);
}
/**
 * Program 17.4 Adjacency-matrix allocation and initialization
 * -------------------------------------------------------------------------------------------------------------
 * This program uses the standard C array-of-arrays representation for the two-dimensional adjacency matrix (see Section 3.7).
 * It allocates `r` rows with `c` integers each, then initializes all entries to the value `val`.
 *
 * The call `MATRIXinit(V, V, 0)` in Program 17.3 takes time proportional to $V^2$ to create a matrix that
 * represents a V-vertex graph with no edges.
 *
 * For small $V$, the cost of $V$ calls to `malloc` might predominate.
 */
int** MATRIXinit(int r, int c, int val) {
    int i;
    int j;
    int** t = malloc(r * sizeof(int*));
    for (i = 0; i < r; i++) {
        t[i] = malloc(c * sizeof(int));
    }
    for (i = 0; i < r; i++) {
        for (j = 0; j < c; j++) {
            t[i][j] = val;
        }
    }
    return t;
}

Edge EDGE(int v, int w) {
    Edge edge;
    edge.v = v;
    edge.w = w;
    return edge;
}

void GRAPHshow(Graph G) {
    int i;
    int j;
    printf("%d vertices, %d edges\n", G->V, G->E);

    //邻接列表
    for (i = 0; i < G->V; i++) {
        printf("%2d:", i);
        for (j = 0; j < G->V; j++) {
            if (G->adj[i][j] == 1) {
                printf(" %2d", j);
            }
        }
        printf("\n");
    }
    // //邻接矩阵
    // for (i = 0; i < G->V; i++) {
    //     printf("%2d:", i);
    //     for (j = 0; j < G->V; j++) {
    //         printf(" %2d", G->adj[i][j]);
    //     }
    //     printf("\n");
    // }
}
/**
 * Program 18.8 Breadth-first search (adjacency matrix)
 * -----------------------------------------------------------------------------------------------------
 * This implementation of `search` for the adjacency-matrix representation is breadth-first search(BFS).
 *
 * To visit a vertex, we scan through its incident edges, putting any edges to unvisited vertices onto
 * the queue of vertices to be visited.
 *
 * We mark the nodes in the order they are visited in a vertex-indexed array `pre`, and
 * build an explicit parent-link representation of the BFS tree (the edges that first take us to each node)
 * in another vertex-indexed array `st`.
 *
 * This code assumes that we add a call to `QUEUEinit`, and code to declare and initialize `st` to
 * `GRAPHsearch` in Program 18.3.
 *
 */
// void bfs(Graph G, Edge e) {
//     int v;
//     int w;
//     QUEUEput(e);
//     while (!QUEUEempty()) {
//         e=QUEUEget();
//         w = e.w;
//         if (pre[w] == -1) {
//             pre[w] = cnt++;
//             st[w] = e.v;
//             for (v = 0; v < G->V; v++) {
//                 if (G->adj[w][v] == 1) {
//                     if (pre[v] == -1) {
//                         QUEUEput(EDGE(w, v));
//                     }
//                 }
//             }
//         }
//     }
// }
/**
 * Program 18.9 Improved BFS
 * ---------------------------------------------------------------------------------------------------------------------
 * To guarantee that the queue that we use during BFS has at most V entries,
 * we mark the vertices as we put them on the queue.
 */
void bfs(Graph G, Edge e) {
    int v;
    int w;
    QUEUEput(e);
    pre[e.w] = cnt++;
    while (!QUEUEempty()) {
        e=QUEUEget();
        w = e.w;
        st[w] = e.v;
        for (v = 0; v < G->V; v++) {
            if (G->adj[w][v] == 1 && pre[v] == -1) {
                QUEUEput(EDGE(w, v));
                pre[v] = cnt++;
            }
        }
    }
}

void print_shortest_pathR(int v, int w) {
    if (v == w) {
        printf("%d", w);
        return;
    }
    // 如果没有父节点（表示路径不通或current_node不是来自source_node的BFS树）
    if (st[v] == -1) {
        // 这是个错误情况，表示 current_node 无法通过 st 追溯到 source_node
        // 应该在调用前检查 pre[dest] != -1
        return;
    }
    print_shortest_pathR(st[v], w); // 递归打印父节点
    printf("-%d", v); // 打印当前节点
}

void print_shortest_path(int v, int w) {
    // 确保目标节点是可达的
    if (pre[w] == -1) {
        printf("No path from %d to %d.\n", v, w);
        return;
    }
    // 调用递归辅助函数
    print_shortest_pathR(w, v);
    printf("\n");
}

//图操作函数实现
Graph GRAPHinit(int V) {
    Graph G = malloc(sizeof(*G));
    G->V = V;
    G->E = 0;
    G->adj = MATRIXinit(V, V, 0);
    return G;
}

void GRAPHinsertE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    if (G->adj[v][w] == 0) {
        G->E++;
    }
    G->adj[v][w] = 1;
    G->adj[w][v] = 1;
}

void GRAPHremoveE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    if (G->adj[v][w] == 1) {
        G->E--;
    }
    G->adj[v][w] = 0;
    G->adj[w][v] = 0;
}
int GRAPHedges(Edge a[], Graph G) {
    int v;
    int w;
    int E = 0;
    for (v = 0; v < G->V; v++) {
        for (w = v+1; w < G->V; w++) {
            if (G->adj[v][w] == 1) {
                a[E++] = EDGE(v, w);
            }
        }
    }
    return E;
}

Graph GRAPHcopy(Graph G) {
    Graph copy = GRAPHinit(G->V);
    int i;
    int j;
    for (i = 0; i < G->V; i++) {
        for (j = 0; j < G->V; j++) {
            if (G->adj[i][j] != 0) {
                GRAPHinsertE(copy, EDGE(i, j));
            }
        }
    }
    return copy;

}

void GRAPHdestroy(Graph G) {
    int i;
    for (i = 0; i < G->V; i++) {
        free(G->adj[i]);
    }
    free(G->adj);
    free(G);
}

void GRAPHsearch(Graph G) {
    HELPinit(G->V);
    int v;
    for (v = 0; v < G->V; v++) {
        if (pre[v] == -1) {
            search(G, EDGE(v,v));
        }
    }

}

void GRAPHsearch2(Graph G, int source) {
    HELPinit(G->V);
    search(G, EDGE(source,source));
}

//测试函数声明
void test_bfs();
void test_shortest_path();

int main(int argc, char *argv[]) {
    // test_bfs();
    test_shortest_path();
    return 0;
}

//测试函数实现
void test_bfs() {
    int V = 8;
    Graph G = GRAPHinit(V);

    Edge edge1 = EDGE(0, 2);
    Edge edge2 = EDGE(0, 5);
    Edge edge3 = EDGE(0, 7);
    Edge edge4 = EDGE(1, 7);
    Edge edge5 = EDGE(2, 6);
    Edge edge6 = EDGE(3, 4);
    Edge edge7 = EDGE(3, 5);
    Edge edge8 = EDGE(4, 5);
    Edge edge9 = EDGE(4, 6);
    Edge edge10 = EDGE(4, 7);

    GRAPHinsertE(G, edge1);
    GRAPHinsertE(G, edge2);
    GRAPHinsertE(G, edge3);
    GRAPHinsertE(G, edge4);
    GRAPHinsertE(G, edge5);
    GRAPHinsertE(G, edge6);
    GRAPHinsertE(G, edge7);
    GRAPHinsertE(G, edge8);
    GRAPHinsertE(G, edge9);
    GRAPHinsertE(G, edge10);

    // GRAPHshow(G);

    GRAPHsearch(G);

    // int i;
    // printf("pre: ");
    // for (i = 0; i < G->V; i++) {
    //     printf("%d ", pre[i]);
    // }
    // printf("\n");
    //
    // printf("st: ");
    // for (i = 0; i < G->V; i++) {
    //     printf("%d ", st[i]);
    // }
    // printf("\n");

    GRAPHdestroy(G);
    HELPcleanUp();
}

void test_shortest_path() {
    int V = 8;
    Graph G = GRAPHinit(V);

    Edge edge1 = EDGE(0, 2);
    Edge edge2 = EDGE(0, 5);
    Edge edge3 = EDGE(0, 7);
    Edge edge4 = EDGE(1, 7);
    Edge edge5 = EDGE(2, 6);
    Edge edge6 = EDGE(3, 4);
    Edge edge7 = EDGE(3, 5);
    Edge edge8 = EDGE(4, 5);
    Edge edge9 = EDGE(4, 6);
    Edge edge10 = EDGE(4, 7);

    GRAPHinsertE(G, edge1);
    GRAPHinsertE(G, edge2);
    GRAPHinsertE(G, edge3);
    GRAPHinsertE(G, edge4);
    GRAPHinsertE(G, edge5);
    GRAPHinsertE(G, edge6);
    GRAPHinsertE(G, edge7);
    GRAPHinsertE(G, edge8);
    GRAPHinsertE(G, edge9);
    GRAPHinsertE(G, edge10);

    //两个顶点之间的最短路径
    // GRAPHsearch2(G, 0);
    // //0到3的最短路径
    // print_shortest_path(0, 3);

    //从单源头出发的所有最短路径
    // int v = 4;
    // GRAPHsearch2(G, v);
    // int w;
    // for (w = 0; w < G->V; w++) {
    //     print_shortest_path(v, w);
    // }

    //所有顶点对的最短路径
    int v;
    int w;
    for (v = 0; v < G->V; v++) {
        GRAPHsearch2(G, v);
        for (w = 0; w < G->V; w++) {
            print_shortest_path(v, w);
        }
    }
}
